package DataStructure.tree;


import DataStructure.linear.Queue;

public class BinaryTree<Key extends Comparable<Key>,Value> {
    private Node root;
    private int N;

    private class Node {
        public Node left;
        public Node right;
        public Key key;
        public Value value;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    public int size() {
        return N;
    }

    //如果根节点为空，则将插入的元素替换为根节点
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    //向指定的树x中添加并返回添加元素后新的树
    public Node put(Node x, Key key, Value value) {
        //如果x子树为空
        if (x == null) {
            N++;
            return new Node(key, value, null, null);
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            //如果key大于x节点的键，则继续找x的右子树
            x.right = put(x.right, key, value);
        } else if (cmp < 0) {
            //如果key小于x节点的键，则继续找x的左子树
            x.left = put(x.left, key, value);
        } else {
            //如果key等于x节点的键，则替换x的value
            x.value = value;
        }

        return x;
    }


    //查询整个数中key对应的value
    public Value get(Key key) {
        Value value = get(root, key);
        return value;
    }

    //查询x树中key对应的value
    public Value get(Node x, Key key) {
        //x树为null
        if (x == null) {
            return null;
        }
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            return get(x.right, key);
        } else if (cmp < 0) {
            return get(x.left, key);
        } else {
            return x.value;
        }
    }


    //删除整个树中key对应的结点
    public void delete(Key key) {
        delete(root, key);
    }

    //删除指定树中key对应的结点,并返回
    public Node delete(Node x, Key key) {
        //x为null
        if (x == null) {
            return null;
        }

        //x不为null
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            //删除x右子树键为key的结点并把删除结点后的x右子树返回成为x的右子树
            x.right = delete(x.right, key);
        } else if (cmp < 0) {
            x.left = delete(x.left, key);
        } else {
            N--;
            //找到右子树中最小的结点
            if (x.right == null) {
                return x.left;
            }
            if (x.left == null) {
                return x.right;
            }
            //如果x的左右都不为空，则找到x的右子树的最小值代替x
            Node minNode = x.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            //删除minNode
            Node n = x.right;
            while (n.left != null) {
                if (n.left.left == null) {
                    n.left = null;
                } else {
                    n = n.left;
                }
            }

            minNode.left = x.left;
            minNode.right = x.right;
            x = minNode;

        }
        return x;
    }


    //查找整个树中最小的键
    public Key min() {
        return min(root).key;
    }

    //在指定数x中最小键所在的节点
    private Node min(Node x) {
        if (x.left != null) {
            return min(x.left);
        } else {
            return x;
        }
    }


    public Key max() {
        return max(root).key;
    }

    public Node max(Node x) {
        if (x.right != null) {
            return max(x.right);
        } else {
            return x;
        }
    }


    //前序遍历
    //获取整个树中所有的键
    public Queue<Key> preErgodic() {
        Queue<Key> prekeys = new Queue<>();
        preErgodic(root,prekeys);
        return prekeys;
    }
    //获取指定树x的所有键斌放入keys的队列中
    private void preErgodic(Node x, Queue<Key> keys){
        if(x==null){
            return;
        }
        //把x节点的key放入keys中
        keys.enqueue(x.key);
        //递归遍历x节点的左子树
        if(x.left!=null){
            preErgodic(x.left,keys);
        }
        //递归遍历x节点的右子树
        if(x.right!=null){
            preErgodic(x.right,keys);
        }
    }


    //中序遍历
    //获取整个树中所有的键
    public Queue<Key> midErgodic() {
        Queue<Key> midkeys = new Queue<>();
        midErgodic(root,midkeys);
        return midkeys;
    }
    //获取指定树x的所有键斌放入keys的队列中
    private void midErgodic(Node x, Queue<Key> keys){
        if(x==null){
            return;
        }
        //先递归，把左子树中的键放入keys中
        if(x.left!=null){
            midErgodic(x.left,keys);
        }
        //把当前节点x的键放入keys中
        keys.enqueue(x.key);
        //再递归把右子树中的键放入keys中
        if(x.right!=null){
            midErgodic(x.right,keys);
        }
    }



    //后序遍历
    //获取整个树中所有的键
    public Queue<Key> afterErgodic() {
        Queue<Key> afterkeys = new Queue<>();
        afterErgodic(root,afterkeys);
        return afterkeys;
    }
    //获取指定树x的所有键斌放入keys的队列中
    private void afterErgodic(Node x, Queue<Key> keys){
        if(x==null){
            return;
        }
        //先递归，把左子树中的键放入keys中
        if(x.left!=null){
            afterErgodic(x.left,keys);
        }
        //再递归把右子树中的键放入keys中
        if(x.right!=null){
            afterErgodic(x.right,keys);
        }
        //把当前节点x的键放入keys中
        keys.enqueue(x.key);
    }


    //使用层次遍历
    public Queue<Key> layerErgodic(){
        //定义两个队列，分别存储树中的键和书中的节点
        Queue<Node> nodes = new Queue<>();
        Queue<Key> keys = new Queue<>();
        //默认往队列中放入根节点
        nodes.enqueue(root);
        while (!nodes.isEmpty()){
            //弹出节点，把key放入keys中
            Node n = nodes.dequeue();
            keys.enqueue(n.key);
            //判断当前节点有没有左子节点，如果有则放入nodes中
            if(n.left!=null){
                nodes.enqueue(n.left);
            }
            //判断当前节点有没有右子节点，如果有则放入nodes中
            if(n.right!=null){
                nodes.enqueue(n.right);
            }
        }
        return keys;
    }


    //获取整个树的最大深度
    public int maxDepth(){
        return maxDepth(root);
    }

    //获取x树的最大深度
    public int maxDepth(Node x){
        if(x==null){
            return 0;
        }
        int max=0;
        int maxL=0;
        int maxR=0;
        //计算x的左子树最大深度
        if(x.left!=null){
            maxL=maxDepth(x.left);
        }
        //计算x的右子树最大深度
        if(x.right!=null){
            maxR=maxDepth(x.right);
        }
        //比较两个值取大的加1即可
        max=maxL>maxR?maxL+1:maxR+1;
        return max;
    }

}
